package com.dlut.java2;

import java.util.*;

/**
 * @Author: LiuHeng
 * @Description:
 * @Date: 2022-09-05 23:56
 */
public class T652_II82 {
    public static void main(String[] args) {
        int[] arr = new int[]{10,1,2,7,6,1,5};
        T652_II82 s = new T652_II82();
        for (List<Integer> list : s.combinationSum2(arr, 8)) {
            System.out.println(list);
        }

    }

    /**
     * 剑指 Offer II 082. 含有重复元素集合的组合
     */
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<Integer> list = new ArrayList<>();
        dfs(candidates, list,0,target);

        return ans;
    }
    void dfs(int[] arr,List<Integer> ll, int index, int target){
        if (arr[index] > target)
            return;
        if (arr[index] == target){
            ll.add(arr[index]);
            ans.add(new ArrayList<>(ll));
            ll.remove(Integer.valueOf(arr[index]));
            return;
        }

        int i = index + 1;
        while (i < arr.length && arr[i] == arr[index]){
            i++;
        }
        if (i != arr.length){
            dfs(arr, ll, i, target);
        }
        if (index + 1 < arr.length){
            ll.add(arr[index]);
            dfs(arr, ll, index+1,target - arr[index]);
            ll.remove(Integer.valueOf(arr[index]));
        }
    }


    /**
     * 652. 寻找重复的子树
     */
    HashMap<String, TreeNode> map = new HashMap<>();
    Set<TreeNode> set = new HashSet<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        fun(root);
        return new ArrayList<>(set);
    }
    String fun(TreeNode node){
        if (node == null)
            return "";
        StringBuffer sb = new StringBuffer();
        sb.append(String.valueOf(node.val));
        sb.append("(");
        sb.append(fun(node.left));
        sb.append(")(");
        sb.append(fun(node.right));
        sb.append(")");
        if (map.containsKey(sb.toString())){
            set.add(map.get(sb.toString()));
        }else {
            map.put(sb.toString(),node);
        }
        return sb.toString();
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

